package chp;

import java.util.Comparator;
import java.util.HashSet;
import java.util.Hashtable;
import java.util.Iterator;
import java.util.PriorityQueue;
import java.util.Vector;

/*
 * This class takes a WICInput object and produces a solution out of it
 * This solution will be returned either as data structure or as file
 * 
 * The algorithm implemented here takes a greedy approach.
 * To build the intervals the algorithm proceeds like this
 * - it finds the minimum number in the sequence
 * - it starts creating the interval from it and extends it towards left and right till when it's possible
 * 
 */

class SolutionGenerator {
	
	static boolean saveTime = false;
	static long treshold = 9000;
	
	static PriorityQueue<int[]> arrayProcessor(int[] arr){
		
		PriorityQueue<int[]> pq = new PriorityQueue<int[]>(arr.length, 
														   new Comparator<int[]>(){
																public int compare(int[] a, int[] b){
																	return (a[1] <= b[1]) ? -1 : 1;
																}
														   	});
		for(int i=0; i<arr.length; i++){
			if(arr[i] == 0) //skip 0s
				continue;
			pq.add(new int[]{i,arr[i]});
		}
		return pq;
	}
	
	
	static WICOutput generateSolutionMin(WICInput inputData){
		
		int[] ySet = inputData.getYSet().clone();
		int n = inputData.getN();
		PriorityQueue<int[]> numbersQueue = arrayProcessor(ySet);
		Vector<int[]> solution = new Vector<int[]>(); // in this Vector we store the solutions (intervals + weight --> int[3])
													  // the first two numbers: interval boundaries, third: weight
		
		int a,b,c = 0; // [a,b] defines the interval, c is the weight
		int[] nextQueueElement = null, queueElement = null;
		
		while(!numbersQueue.isEmpty()){
			
			queueElement = numbersQueue.poll();
			while(ySet[queueElement[0]] < queueElement[1]){
				if(ySet[queueElement[0]] != 0)
					numbersQueue.add(new int[]{queueElement[0],ySet[queueElement[0]]});	
				queueElement = numbersQueue.poll();
				if(queueElement == null) //only 0s
					return new WICOutput(solution,solution.size());
			}
			
			nextQueueElement = (numbersQueue.size() != 0) ? numbersQueue.peek() : null;
			while(nextQueueElement != null && ySet[ nextQueueElement[0] ] < nextQueueElement[1]){
				numbersQueue.poll(); //throw away the element
				if(ySet[ nextQueueElement[0] ] != 0)
					numbersQueue.add(new int[]{nextQueueElement[0],ySet[ nextQueueElement[0] ]});
				nextQueueElement = numbersQueue.peek();
			}
			
			a = queueElement[0];
			b = a + 1;
			c = ySet[queueElement[0]];
			
			//update the element
			ySet[a] = ySet[a] - c;
			
			//try to extend it to the left
			while( (a > 0) && (ySet[a-1] >= c) ){
				a--;
				ySet[a] = ySet[a] - c;
				if(nextQueueElement != null && ySet[a] < nextQueueElement[1])
					if(ySet[a] != 0)
						numbersQueue.add(new int[]{a,ySet[a]});	
			}
			//try to extend it to the right
			while( (b < n) && (ySet[b] >= c) ){
				ySet[b] = ySet[b] - c;
				if(nextQueueElement != null && ySet[b] < nextQueueElement[1])
					if(ySet[b] != 0)
						numbersQueue.add(new int[]{b,ySet[b]});
				b++;
			}
			
			//add the triple to the solution set. Adjust the values too
			solution.add(new int[]{a+1,b+1,c});
		}
		
		return new WICOutput(solution,solution.size());
	}
	
	
	static WICOutput generateSolutionMax(WICInput inputData){
		int[] ySet = inputData.getYSet().clone(); 
		int n = inputData.getN();
		
		Vector<int[]> solution = new Vector<int[]>(); // in this Vector we store the solutions (intervals + weight --> int[3])
													  // the first two numbers: interval boundaries, third: weight
		
		
		int a,b,c = 0; // [a,b] defines the interval, c is the weight
		int indexOfMax = 0;
		int indexOfMaxNeighborLEFT = 0, indexOfMaxNeighborRIGHT = 0;
		
		while(true){
			
			indexOfMax = 0;
			
			// _Step 1_: find the index of the maximum number
			for(int i=1; i<n; i++)
				if(ySet[i] > ySet[indexOfMax])
					indexOfMax = i;
			
			if(ySet[indexOfMax] == 0) //this means that the algorithm can terminate, all the numbers are 0
				break;
			
			// _Step 2_: find the biggest neighbor and create the interval. We extend the interval
			//			 if the sorrounding numbers are equal to ySet[indexOfMax] 
			a = indexOfMax;
			b = indexOfMax + 1;
			c = 0; //weight
			
			//let's look at the left for equal numbers
			while( (a > 0) && (ySet[a-1] == ySet[indexOfMax]) )
				a--;
			if(a-1 < 0) //we reached the limit at the left
				indexOfMaxNeighborLEFT = -1;
			else
				indexOfMaxNeighborLEFT = a-1;
			
			//let's look at the right for equal numbers
			while( (b < n) && (ySet[b] == ySet[indexOfMax]) )
				b++;
			if(b > n-1) //we reached the limit at the right
				indexOfMaxNeighborRIGHT = -1;
			else
				indexOfMaxNeighborRIGHT = b;
			
			//the weight of the interval is chosen to "level" the numbers to the max neighbor
			if( indexOfMaxNeighborLEFT == -1 && indexOfMaxNeighborRIGHT == -1 ) //covered the entire sequence
				c = ySet[indexOfMax];
			else if(indexOfMaxNeighborLEFT == -1)
				c = ySet[indexOfMax] - ySet[indexOfMaxNeighborRIGHT];
			else if(indexOfMaxNeighborRIGHT == -1)
				c = ySet[indexOfMax] - ySet[indexOfMaxNeighborLEFT];
			else if( ySet[indexOfMaxNeighborLEFT] >= ySet[indexOfMaxNeighborRIGHT])
				c = ySet[indexOfMax] - ySet[indexOfMaxNeighborLEFT];
			else
				c = ySet[indexOfMax] - ySet[indexOfMaxNeighborRIGHT];
			
			//update the values covered by the interval
			for(int i=a; i<b; i++)
				ySet[i] = ySet[i] - c;
			
			//add the triple to the solution set. Adjust the values too
			solution.add(new int[]{a+1,b+1,c});
		}
		
		return new WICOutput(solution,solution.size());
	}
	
	class QElement{
		private final int y;
		private final PriorityQueue<Integer> occurrences;
		private int lastOccurrence;
		
		QElement(int n, int firstOcc){
			this.y = n;
			this.occurrences = new PriorityQueue<Integer>(10,new Comparator<Integer>(){
				public int compare(Integer a, Integer b){
					return (a.intValue() < b.intValue()) ? -1 : 1;
				}
			});
			occurrences.add(firstOcc);
			lastOccurrence = firstOcc;
		}

		int getY() {
			return y;
		}
		
		int getMultiplicity() {
			return occurrences.size();
		}

		int getFirstOccurence() {
			return occurrences.peek();
		}

		int getLastOccurrence(){
			return lastOccurrence;
		}
		
		void addOccurrence(int index){
			this.occurrences.add(new Integer(index));
			if(index > lastOccurrence)
				this.lastOccurrence = index;
		}
		
		void removeOccurrence(int index){
			this.occurrences.remove(new Integer(index));
			if(index == lastOccurrence){
				Iterator<Integer> it = occurrences.iterator();
				this.lastOccurrence = getFirstOccurence();
				while(it.hasNext())
					this.lastOccurrence = Math.max(lastOccurrence, it.next());
			}
		}
		
		PriorityQueue<Integer> getOccurrences() {
			return occurrences;
		}

	}
	
	class Comp implements Comparator<QElement>{

		public int compare(QElement a, QElement b){
			if(a.getMultiplicity() == 1 && b.getMultiplicity() == 1)
				return 0;
			else if(a.getMultiplicity() == 1)
				return 1;
			else if(b.getMultiplicity() == 1)
				return -1;
			else //multiplicities are different
				return (a.getY() > b.getY()) ? 1 : -1;
		}
		
	}
	
	static WICOutput equalNumbersFirst(WICInput inputData){
		long time = 0;
		if(saveTime)
			time = System.currentTimeMillis();
		
		SolutionGenerator sl = new SolutionGenerator();
		int[] ySet = inputData.getYSet().clone(); 
		Vector<int[]> solution = new Vector<int[]>();
		QElement value = null;
		Hashtable<Integer, QElement> htable = findMultiplicities(ySet, sl);
		
		if(htable.size() == 0)// we are done, only 0s
			return new WICOutput(solution, solution.size());
		
		QElement temp = null;
		PriorityQueue<QElement> pq = null;
		HashSet<int[]> ts = null;
		int status = 0;
		int[] interval;
		int a,b,c;
		HashSet<Integer> blackList = new HashSet<Integer>();
		int[] modifiedInterval = null;
		
		
		while(true){
			if(saveTime && System.currentTimeMillis() - time >= treshold)
				status = 2;
			
			switch(status){
			
			case 0: // scan the input sequence
				
				if(htable.size() == 0)// we are done, only 0s
					return new WICOutput(solution, solution.size());
				
				pq = new PriorityQueue<QElement>(htable.size(), sl.new Comp());
				pq.addAll(htable.values());
				status = 1;
				
				break;
				
			case 1: //extract elements from the queue and find the intervals
				if(pq.size() == 0) 
					return new WICOutput(solution, solution.size());
				
				modifiedInterval = createModifiedInterval(ts);
				
				temp = pq.poll();
				
				while(true){
					if(modifiedInterval != null){
						if(isInBlackInterval(temp,modifiedInterval)){
							blackList.remove(temp.getY());
							break;
						}
						else if(isBlackListed(temp, blackList))
							temp = pq.poll();
						else
							break;
					}
					else if(isBlackListed(temp, blackList))
						temp = pq.poll();
					else 
						break;
				}
				
				if(temp.getMultiplicity() == 1){
					status = 2;
					break;
				}
				// Let's throw away the first element now		

				//here we get the intervals
				ts = findIntervals(ySet,temp.getFirstOccurence(),temp.getMultiplicity()-1,temp.getY());

				if(ts.size() == 0 && pq.size() != 0)//empty set :(
					blackList.add(temp.getY());//let's try our luck with the next QElement - status = 1 here
				else if(ts.size() == 0 && pq.size() == 0){
					status = 2;
					break;
				}					
				else{
					Iterator<int[]> iter = ts.iterator();
					
					while(iter.hasNext()){
								
						interval = iter.next();
						a = interval[0];
						b = interval[1];
						c = temp.getY();
				
						//update the values covered by the intervals
						for(int i=a; i<=b; i++){
							
							// 1) update the hash table removing the old value
							value = htable.get(ySet[i]);
							if(value.getMultiplicity() == 1) //if this was the last one of his kind... bye!
								htable.remove(ySet[i]);
							else{
								value.removeOccurrence(i);
								htable.put(ySet[i],value);
							}
						
							// 2) update the value
							ySet[i] = ySet[i] - c;
						
							// 	3) update the hash table with the new value
							value = htable.get(ySet[i]);
							if(value == null && ySet[i] != 0){
								value =  sl.new QElement(ySet[i],i);
								htable.put(ySet[i],value);
								blackList.remove(ySet[i]);
							}
							else if(value != null){
								value.addOccurrence(i);
								htable.put(ySet[i],value);
								blackList.remove(ySet[i]);
							}
						}
							
						//add the triple to the solution set. Adjust the values too
						solution.add(new int[]{a+1,b+2,c});
					}
					status = 0; //let's go back to regenerate the data
				}
				break;
			
			case 2: // pass the control to generateSolutionMin()
				WICOutput partialSol = generateSolutionMin(new WICInput(inputData.getN(), inputData.getK(), ySet));
				solution.addAll(partialSol.getData());
				return new WICOutput(solution,solution.size());
			}
		}
	}

	
	private static boolean isBlackListed(QElement el, HashSet<Integer> blackList){
		return blackList.contains(el.getY());
	}


	private static int[] createModifiedInterval(HashSet<int[]> intervalSet){
		if (intervalSet == null)
			return null;
		
		Iterator<int[]> it = intervalSet.iterator();
		int[] interval = new int[]{-1,-1};
		int[] temp;
		
		while(it.hasNext()){
			temp = it.next();
			interval[0] = (interval[0] == -1) ? temp[0] : Math.min(temp[0], interval[0]);
			interval[1] = (interval[1] == -1) ? temp[1] : Math.max(temp[1], interval[1]);
		}
		return (interval[0] == -1) ? null : interval;
	}
	
	
	
	private static boolean isInBlackInterval(QElement el, int[] blackInt){
		if(blackInt[0] > el.getLastOccurrence() || blackInt[1] < el.getFirstOccurence())
			return false;
		
		return true;
	}
	
	
	
	private static Hashtable<Integer, QElement> findMultiplicities(int[] ySet, SolutionGenerator sl){
		
		Hashtable<Integer, QElement> htable = new Hashtable<Integer, QElement>();
		QElement value = null;
		
		for(int i=0; i<ySet.length; i++){
			
			if(ySet[i] == 0) //skip 0s
				continue;
			
			if(htable.containsKey(ySet[i]))
				value = htable.get(ySet[i]);
			else
				value = null;
			
			//update multiplicity
			if(value==null)
				value = sl.new QElement(ySet[i],i);
			else
				value.addOccurrence(i);
			
			//insert in the table the new value
			htable.put(ySet[i], value);
		}
		
		return htable;
	}
	
	
	/*
	 * method that finds all the intervals that cover at least two occurences of the given y
	 */
	private static HashSet<int[]> findIntervals(int[] ySequence, int indexFirstY, int mult, int y){
		int indexOfFirstY = indexFirstY; // stores the index of the first y
		int indexOfSecondY= 0; // records the next y that we are trying to reach
		int multiplicity = mult;
		
		int status = 0; //used to let the algorithm to perform different tasks in the execution
		boolean seeEachOther = true; //used to understand if there is any number n<y between the two y
		boolean coveredAtLeastTwoYi = false;
		int[] interval = new int[2]; //stores the interval that we have found
		int tmpIndex = -1; //temp variable used for mixed purposes
		HashSet<int[]> intervalsSet = new HashSet<int[]>(); //here we store the set of intervals
		
		while(true){
			switch(status){
		
			case 0:
				coveredAtLeastTwoYi = false;
				seeEachOther = true;
				//try to extend the interval to the left
				tmpIndex = indexOfFirstY;
				while( (tmpIndex > 0) && (ySequence[tmpIndex-1] >= y) ) 
					tmpIndex--;
				//update our interval
				interval[0] = tmpIndex;
				interval[1] = indexOfFirstY;
				//no break since when we start from case 0 the subsequent step will always be case 1 ;)
				
			case 1:
				multiplicity--; //we are proceeding towards the next y. "register" this event
				
				//find the next occurrence of y and see also if the interval can be created
				tmpIndex = indexOfFirstY;//records until which index we arrive, in case !seeEachOther
				indexOfSecondY=indexOfFirstY+1; //records the index of the next occurrence of Y
				for(; indexOfSecondY<ySequence.length; indexOfSecondY++){
					if(ySequence[indexOfSecondY] == y)
						break;
					if(ySequence[indexOfSecondY] > y && seeEachOther)
						tmpIndex++;
					else
						seeEachOther = false;
				}
				
				if(seeEachOther){ //we can make the interval between indexOfFirstY and indexOfSecondY
					if(multiplicity == 0){// if this was the last y...
						tmpIndex = indexOfSecondY;//... first let's see if we can go to the right some more
						while( (tmpIndex < ySequence.length-1) && (ySequence[tmpIndex+1] >= y) )
							tmpIndex++;

						interval[1] = tmpIndex;
						intervalsSet.add(interval);
						return intervalsSet;
					}
					else{
							coveredAtLeastTwoYi = true;
							status = 1;
					}
				}
				else{ // they don't "see" each other
					if(!coveredAtLeastTwoYi){
						if(multiplicity == 0) //only one yi remaining
							return intervalsSet;
					}
					else{
						interval[1] = tmpIndex;
						intervalsSet.add(interval);
						if(multiplicity == 0)
							return intervalsSet;
					}
					status = 0;
				}
				indexOfFirstY = indexOfSecondY;
				break;
			}
		}
	}
}